package linkedList;

/**
 * 合并两个有序链表(简单)
 *
 * @author yyz
 * @create 2023-11-07 9:14
 */
public class 合并两个有序链表 {
    public static void main(String[] args) {
        ListNode list1 = ListNode.of(1, 2, 3, 4);
        ListNode list2 = ListNode.of(1, 2, 5);

        System.out.println(new 合并两个有序链表().mergeTwoLists1(list1, list2));
    }

    private ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        // 创建一个虚拟节点
        ListNode s = new ListNode(-1);
        // 指针p指向该虚拟节点
        ListNode p = s;

        // 遍历链表，将两个链表中较小的值添加到新链表中
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                s.next = list1;
                list1 = list1.next;
            } else {
                s.next = list2;
                list2 = list2.next;
            }
            // 更新指针s
            s = s.next;
        }

        // 将剩余部分添加到新链表中
        s.next = (list1 != null ? list1 : list2);

        // 返回新链表的头节点
        return p.next;
    }


    private ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) { // 如果list1为空，说明list1已经遍历完了，直接返回list2剩余部分即可
            return list2;
        }
        if (list2 == null) { // 如果list2为空，说明list2已经遍历完了，直接返回list1剩余部分即可
            return list1;
        }
        if (list1.val <= list2.val) { // 如果list1的值小于等于list2的值
            list1.next = mergeTwoLists2(list1.next, list2); // 递归地将list1的下一个节点和list2合并，并将结果连接到list1后面
            return list1; // 返回list1作为合并后的头部
        } else { // 如果list2的值小于list1的值
            list2.next = mergeTwoLists2(list1, list2.next); // 递归地将list1和list2的下一个节点合并，并将结果连接到list2后面
            return list2; // 返回list2作为合并后的头部
        }

    }
}
